package com.sheepone.util.structure.tree.binary;

import com.sheepone.util.ArrayUtil;
import com.sheepone.util.algorithm.analysis.IntegerAnalysisUtil;

import java.util.*;

/**
 * @author Miss.杨
 * @description
 * @since 2024/5/6:21:51
 */
public class Heap<E extends Comparable<? super E>> extends IndexedBinaryTree<E> {
    private final Comparator<E> comparator;

    public Heap() {
        this((E[]) null, Integer.MAX_VALUE, Comparator.naturalOrder());
    }

    public Heap(int capacity) {
        this((E[]) null, capacity, Comparator.naturalOrder());
    }

    public Heap(Comparator<E> comparator) {
        this((E[]) null, Integer.MAX_VALUE, comparator);
    }

    public Heap(Collection<E> elements) {
        this(elements, Integer.MAX_VALUE, Comparator.naturalOrder());
    }

    public Heap(E[] elements) {
        this(elements, Integer.MAX_VALUE, Comparator.naturalOrder());
    }

    public Heap(int capacity, Comparator<E> comparator) {
        this((E[]) null, capacity, comparator);
    }

    public Heap(Collection<E> elements, Comparator<E> comparator) {
        this(elements, Integer.MAX_VALUE, comparator);
    }

    @SuppressWarnings("unchecked")
    public Heap(E[] elements, int capacity, Comparator<E> comparator) {
        super(capacity);
        // 此处不能直接通过new Object[]来初始化数组
        this.elements = (E[]) new Comparable[capacity];
        this.comparator = comparator;
        if (elements != null && elements.length > 0) {
            heapify(elements);
        }
    }

    @SuppressWarnings("unchecked")
    public Heap(Collection<E> elements, int capacity, Comparator<E> comparator) {
        super(capacity);
        // 此处不能直接通过new Object[]来初始化数组
        this.elements = (E[]) new Comparable[capacity];
        this.comparator = comparator;
        if (elements != null && !elements.isEmpty()) {
            heapify(elements);
        }
    }


    /**
     * 建堆
     *
     * @param elements
     */
    private void heapify(Collection<E> elements) {
        elements.forEach(this::offer);
    }

    private void heapify(E[] elements) {
        System.arraycopy(elements, 0, this.elements, size, elements.length);
        size += elements.length;
        // 找到最后一个非叶子节点,从后向前，对每个节点执行下潜
        for (int i = getParentIndex(size - 1); i >= 0; i--) {
            down(i);
        }
    }

    private boolean isPriority(int a, int b) {
        return comparator.compare(elements[a], elements[b]) > 0;
    }

    private int getPriorityIndex(int l, int r, int p) {
        if (l >= size && r >= size) {
            return p;
        }
        int max = p;
        if (isEffectiveIndex(l) && isPriority(l, max)) {
            max = l;
        }
        if (isEffectiveIndex(r) && isPriority(r, max)) {
            max = r;
        }
        return max;
    }

    /**
     * 将当前索引位置的元素进行下潜
     *
     * @param index 索引
     */
    public void down(int index) {
        // 获取当前节点及其孩子节点中优先级最高的节点
        int priorityIndex = getPriorityIndex(getLeftChildIndex(index), getRightChildIndex(index), index);
        if (priorityIndex != index) { // 孩子节点中优先级比当前节点高
            // 下潜
            ArrayUtil.swap(elements, priorityIndex, index);
            // 继续下潜当前节点值
            down(priorityIndex);
        }
    }

    /**
     * 向堆中添加元素
     *
     * @param element 待添加元素
     * @return 是否成功添加
     */
    public boolean offer(E element) {
        if (isFull()) {
            return false;
        }
        int child = size++;
        elements[child] = element;
        int parent = getParentIndex(child);
        while (child > 0 && isPriority(child, parent)) {
            // 子节点上浮，父节点下浮
            ArrayUtil.swap(elements, child, parent);
            child = parent;
            parent = getParentIndex(child);
        }
        elements[child] = element;
        return true;
    }

    /**
     * 从堆中取出堆顶元素
     *
     * @return 堆顶元素
     */
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        // 将堆顶元素与末尾元素交换（数组从尾部移除元素效率最高）
        ArrayUtil.swap(elements, 0, size - 1);
        E element = elements[--size];
        down(0);
        return element;
    }

    public boolean replace(E e) {
        if (isEmpty()) {
            return false;
        }
        elements[0] = e;
        down(0);
        return true;
    }

    /**
     * 从堆中获取堆顶元素
     *
     * @return 堆顶元素
     */
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return elements[0];
    }

    @Override
    public List<List<E>> layerTransfer() {
        int depth = this.layers();
        int index = 0, len;
        ArrayList<List<E>> transfer = new ArrayList<>();
        for (int i = 0; i < depth && index < size; i++) {
            len = 1 << i;
            ArrayList<E> list = new ArrayList<>();
            while (len-- > 0 && index < size) {
                list.add(elements[index++]);
            }
            transfer.add(list);
        }
        return transfer;
    }

    @Override
    public int layers() {
        // each layer nodes ：1    2   4   8   16
        // total nodes      ：1    3   7   15  31
        // total layers     ：1    2   3   4   5
        int level = (int) (Math.log(IntegerAnalysisUtil.upper2Pow(size)) / Math.log(2));
        if (IntegerAnalysisUtil.isPowerOfTwo(size)) {
            level++;
        }
        return level;
    }

    /**
     * 堆排序(倒排)
     *
     * @return 排序后的结果
     */
    public E[] reverseSort() {
        Heap<E> heap = new Heap<>(Arrays.copyOf(elements, size), size, comparator);
        // 将堆顶与堆尾（逐渐缩小）交换，然后对堆顶元素进行下潜
        while (heap.size > 1) {
            ArrayUtil.swap(heap.elements, 0, --heap.size);
            heap.down(0);
        }
        return heap.elements;
    }

    public static void main(String[] args) {
        Heap<Integer> heap = new Heap<>(new Integer[]{2, 3, 1, 7, 8, 9, 6, 4, 5}, 10, (o1, o2) -> o1 - o2);
        heap.layerTransfer().forEach(System.out::println);
        System.out.println(Arrays.toString(heap.reverseSort()));
        System.out.println(heap.maxDepth());
        System.out.println(heap.minDepth());
        System.out.println(heap.isSymmetrical());
    }


}
